CCPC 厦门 2019 VP
打不过隔壁重邮的 CQU 上一次拿金牌的传奇之战。
居然都已经六年了吗。。。
A - Zayin and Bus
签到题，依旧是手速比 yhn 写的。
不管了。
D - Zayin and Forest
题中的函数就是 $\text{lowbit}(x)$
需要知道树状数组是怎么建树的。
往上加的操作只需要一个计数器统计一下下面的贡献就行。
求和操作完全和正常树状数组相同。
但是这个 $x$ 比较大，又要卡 $O(n \log n)$ 的时间。
所以用一个手写的哈希表优化就行。还好我带了哈希表板子.jpg
G - Zayin and Count
lxy 和 yhn 写的，大概可以数位 dp，我不是很会。
H - Zayin and Obstacles
开始的时候都看漏了 Obstacle s
有点唐。
总之就直接高维差分 + 高位前缀和维护一下每一个点是不是能过。
然后 bfs 一下就行了。
真不知道这种送的题为什么我们三个小时才过。
I - Zayin and Coin Game
似乎是一个由很多套路集合在一起的题。
首先转化题意就是，令 $\{C_n\} = \{A_n\} \text{ xor } \{B_n\}$。
然后目的就是通过每次对一个长度为 $k$ 的环上段异或 $1$，将 $\{C_n\}$ 变为全零。
异或是可以差分的，所以问题转化为每次可以选取距离固定的两个点异或，最后让 $\{C_n\}$ 变成全零（异或前缀和为零的充分条件就是全部为零）。
还有另一个经典结论：
将环分为 $g = \gcd(n, k)$ 个模 $g$ 的同余类，那 $t, t + k$ 必属于同一个类，换句话说每次操作只影响一个类。
于是只需要 check 一下每个类是不是都有偶数个 $1$ 即可。
环上的差分只需要记 $c_0 = c_n$ 即可（下标从 $1$ 开始）
J - Zayin and Tree
lxy 的做法是树上 dp。
我感觉可以点分治。